#define _CRT_SECURE_NO_WARNINGS 1

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* rhead = NULL;
    struct ListNode* cur = head;
    struct ListNode* next = NULL;

    while (cur)
    {
        next = cur->next;
        cur->next = rhead;
        rhead = cur;
        cur = next;

    }
    return rhead;
}

struct ListNode* deleteMiddle(struct ListNode* head) {
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    if (fast->next == NULL)
    {
        head = NULL;
        return head;
    }
    while (fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;

    }

    return slow;
}


bool isPalindrome(struct ListNode* head) {
    struct ListNode* mid = deleteMiddle(head);
    struct ListNode* rmid = reverseList(mid);

    while (head && rmid)
    {
        if (head->val == rmid->val)
        {
            head = head->next;
            rmid = rmid->next;
        }
        else
        {
            return false;
        }
    }
    return true;
}